import java.util.Deque;
import java.util.LinkedList;

/**
 * @author hewei
 * @version 1.0
 * @description: 周赛314 t3
 * @date 2022/10/9 11:06
 */

public class RobotWithString {

    public static void main(String[] args) {
        System.out.println(new RobotWithString().robotWithString("bdda"));
    }

    public String robotWithString1(String s) {
        int n = s.length();
        if (n == 1) return s;
        int[] temp = new int[n];
        int index = n - 1;
        temp[n - 1] = -1;
        for (int i = n - 2; i >= 0; i--) {
            temp[i] = index;
            if (s.charAt(i) <= s.charAt(index)) index = i;
        }
        StringBuilder ans = new StringBuilder();
        StringBuilder a = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (temp[i] == -1 || s.charAt(temp[i]) < c) {
                a.append(c);
            } else {
                ans.append(c);
                while (a.length() != 0 && a.charAt(a.length() - 1) <= s.charAt(temp[i])) {
                    ans.append(a.charAt(a.length() - 1));
                    a.deleteCharAt(a.length() - 1);
                }
            }
        }
        ans.append(a.reverse());
        return ans.toString();
    }

    public String robotWithString(String s) {
        int n = s.length();
        if (n == 1) return s;
        int[] temp = new int[n];
        int index = n - 1;
        temp[n - 1] = -1;
        for (int i = n - 2; i >= 0; i--) {
            temp[i] = index;
            if (s.charAt(i) <= s.charAt(index)) index = i;
        }
        StringBuilder ans = new StringBuilder();
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            char a = temp[i] == -1 ? '~' : s.charAt(temp[i]);
            stack.addFirst(c);
            while (!stack.isEmpty() && stack.peekFirst() <= a) ans.append(stack.pollFirst());
        }
        while (!stack.isEmpty()) ans.append(stack.pollFirst());
        return ans.toString();
    }
}